package org.example.sword2offer.primary;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author: lynn
 * @Descript: leetcode 322 零钱兑换，编写一个函数来计算可以凑成总金额所需的最少的硬币个数 最优化问题一般考虑动态规划，因为不是确定的零钱样式
 * @date: 2021/6/27 22:28
 * @version: 1.0
 */
public class Q74_FindAnyCoinMoney {
    public static void main(String[] args) {
        int[] coins={186,419,83,408};
        int amout=6249;
        Q74_FindAnyCoinMoney findAnyCoinMoney=new Q74_FindAnyCoinMoney();
        System.out.println(findAnyCoinMoney.coinChange(coins,amout));

    }

   // fixme 题解07:53  https://www.bilibili.com/video/BV1cT4y1w7Ct?from=search&seid=2941701713750152698

    public int coinChange(int[] coins, int amount) {
        if(amount==0) return 0;
        List<Integer> list=new ArrayList<>();
        for(int i=0;i<coins.length;i++){
            list.add(coins[i]);
        }
        Collections.sort(list);
        int count=0;
        for(int i=list.size()-1;i>=0;i--){
            int tmpCount=amount/list.get(i);
            int restMount=amount%list.get(i);
            if(tmpCount>0 && restMount>=0){
                count+=tmpCount;
                amount=restMount;
            }
            if(i==0&&restMount!=0){
                count=-1;
                return count;
            }
        }
        return count;
    }
}
